/*
  解法：双指针pA和pB
  为什么：本质是道数学题，Leetcode官方题解有详细证明
  时间复杂度：O(m + n)，空间复杂度：O(1)
 */

#include <iostream>
#include <vector>

using namespace std;

// 单链表结构定义
struct ListNode
{
	int val;
	ListNode* next;
	
	ListNode(int x) : val(x), next(nullptr) {}
};

class Solution
{
public:
	ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
	{
		if (headA == nullptr || headB == nullptr)
		{
			return nullptr;		//其中至少有一个链表为空，则两个链表一定不相交
		}
		
		ListNode* pA = headA;
		ListNode* pB = headB;
		
		while (pA != pB)
		{
			if(pA == nullptr)
			{
				pA = headB;
			}
			else
			{
				pA = pA->next;
			}
			
			if(pB == nullptr)
			{
				pB = headA;
			}
			else
			{
				pB = pB->next;
			}
		}
		
		return pA;  // 或 nullptr（两个链表不相交时）
	}
};

// 构建链表（返回首节点和尾节点引用）
ListNode* buildList(const vector<int>& vals)
{
	ListNode* dummy = new ListNode(-1);
	ListNode* tail = dummy;
	
	for (size_t i = 0; i < vals.size(); ++i)
	{
		tail->next = new ListNode(vals[i]);
		tail = tail->next;
	}
	
	ListNode* head = dummy->next;
	delete dummy;
	return head;
}

// 打印链表
void printList(ListNode* head)
{
	while (head != nullptr)
	{
		cout << head->val;
		if (head->next != nullptr)
		{
			cout << " -> ";
		}
		head = head->next;
	}
	cout << endl;
}

// 释放链表内存（不会释放交叉部分）
void deleteList(ListNode* head, ListNode* stopAt = nullptr)
{
	while (head != stopAt)
	{
		ListNode* temp = head;
		head = head->next;
		delete temp;
	}
}

int main()
{
	// 构造公共部分：8 -> 4 -> 5
	ListNode* common = buildList({8, 4, 5});
	
	// 构造链表A：4 -> 1 -> common
	ListNode* listA = buildList({4, 1});
	ListNode* tailA = listA;
	while (tailA->next != nullptr)
	{
		tailA = tailA->next;
	}
	tailA->next = common;  // 拼接公共部分
	
	// 构造链表B：5 -> 0 -> 1 -> common
	ListNode* listB = buildList({5, 0, 1});
	ListNode* tailB = listB;
	while (tailB->next != nullptr)
	{
		tailB = tailB->next;
	}
	tailB->next = common;  // 拼接公共部分
	
	// 打印两个链表
	cout << "链表 A: ";
	printList(listA);
	
	cout << "链表 B: ";
	printList(listB);
	
	// 求交点
	Solution sol;
	ListNode* intersection = sol.getIntersectionNode(listA, listB);
	
	if (intersection != nullptr)
	{
		cout << "交点值为: " << intersection->val << endl;
	}
	else
	{
		cout << "无交点" << endl;
	}
	
	// 释放内存（注意交叉部分只释放一次）
	deleteList(listA, common);
	deleteList(listB, common);
	deleteList(common);
	
	return 0;
}


